package array;

/**
 * @Author quan
 * @Description Num209:长度最小的子数组。
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
 * 如果不存在符合条件的子数组，返回0。 * 输入：target = 7, nums = [2,3,1,2,4,3] * 输出：2 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * @Date 2023/4/25 17:34
 */
public class Demo4_minSubArrayLen {
    /**
     * 暴力解法：两个for循环
     * @param target
     * @param nums
     * @return
     */
//    public int minSubArrayLen(int target, int[] nums) {
////        //result中存储的一定是当前情况下的最小长度
////        int result = Integer.MAX_VALUE;
////        int sum = 0;
////        int subLength = 0;
////        //第一个for循环的i表示从当前子数组的开始位置
////        for (int i = 0; i < nums.length; i++) {
////            sum = 0;
////           //第二个for循环表示当前子数组的终止位置
////            for (int j = i; j < nums.length; j++) {
////                sum = nums[j] + sum;
////                //如果获取到大于等于target的值，则取该子数组的长度与result比较
////                if(sum >= target){
////                    //获取当前的满足条件的子数组的长度
////                    subLength = j-i+1;
////                    //判断是否要更新result中的值
////                    result = Math.min(result, subLength);
////                    //已将这一次循环中满足条件的最小子数组，跳出内层循环
////                    break;
////                }
////            }
////        }
////        //遍历完双层for循环，看result的值有没有被更新；如果还是初始化值，则说明不存在符合条件的最小子数组返回0，否则返回result
////        return (result == Integer.MAX_VALUE ? 0 : result);
////    }

    /**
     * 滑动窗口法：此时循环遍历数组的指针j一定是表示的是满足条件子数组的终止位置
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        //关键在于子数组的开始位置怎么确定？这就是滑动窗口的关键：其实也是一个动态变化的过程
        //定义一些需要使用到的中间变量
        int sum = 0;
        int subLength = 0;
        int result = Integer.MAX_VALUE;
        int i = 0;
        //指针j表示的是指向满足条件的子数组的终止位置
        for (int j = 0; j < nums.length; j++) {
            sum = sum + nums[j];
            //计算当前数组的总和,一旦大于目标值，就计算当前子数组的长度并更新result中的值
            while (sum >= target){
                subLength = j-i+1;
                result = Math.min(subLength,result);
                //这里是滑动窗口的关键！一旦找到满足条件的子数组，此时子数组的开始位置就发生变更，右移一位.同时子数组的和也要更新.
                //相当于又重新缩小了子数组的范围再不断的重新判断
                sum = sum - nums[i];
                i ++;
            }
            //一旦子数组的长度不满足目标值，则就跳出了while循环。此时j再右移
        }
        //判断result的值从而确定数组长度
        return (result == Integer.MAX_VALUE ? 0 : result);
    }
}
